关于Dilworth定理的证明
Dilworth定理1
对于一个DAG而言，最小链覆盖的数量=最长反链的长度
设$G=(V,E)$，最长反链长度=$k$，$|V|=n$
设最小链覆盖中划分为$S_C=\{C_1\dots C_k\}$这k条互不相交的链，$C_i$中的元素为$\{a_{i,j}\}$
设最长反链有$r$条为$S_A=\{A_1\dots A_r\}$，且$A_i$中的元素为$\{b_{i,j}\}$
第一步，证明$k\leq|S_C|$
根据最小链覆盖的性质，$\forall_{C_i\in S_C,C_j\in S_C,i\not =j},存在 a_{i,x}与a_{j,y}不可比(*)$，不然这两条链完全可以合并，不符合最小链覆盖的定义
如果$k>|S_C|$，那么根据抽屉原理，总会有两个一条反链中的元素处在同一条链中，二者可比，与假设不符
因此$k\leq|S_C|$
第二步，证明$k= |S_C|$
(1)当$|V|=0$和$|V|=1$的时候命题显然成立；
(2)设当$|V|<n$时命题均成立；
(3)只需证明当$|V|=n$时命题成立即可
由于$G$是DAG，那么一定有一个极大元，设为$X$；考虑$G’=G-X$，其他定义同上
3.1 证明$|S_C’|\leq |S_C|\leq |S_C’|+1$
显然，$|S_C|\geq |S_C’|$，由于$X$是极大元，不可能把两条链合并；
并且$|S_C|\leq |S_C’|+1$，把$X$单独成链，就是一种一定可行构造方案，其他的方案均不是最小
3.2 证明当$|V|=n$命题成立
令$B=\{maxC’_1,maxC’_2,\dots,maxC’_{k’}\}$，$B$一定是反链，若其中两个元素可比，则与(*)相悖
1‘ 如果$B$中的元素和$X$都不可比，那么$k=k’+1$，又因为$k=k’+1=|S_C’|+1\leq|S_C|,|S_C|\leq |S_C’|+1$，故$|S_C|=|S’_C|+1$，$|S_C| =k$成立
2’ 如果$B$中有元素和$X$可比，设其中之一为$b_i$，那么$C’_i\bigcup X$是一条链，（$b_i$是max了），$G’-C’_i$的最小链覆盖变为$k’-1$，由前文的假设，最长反链也是$k’-1$
说明：如果$G’-C’_i$能构造出更小的方案，那么$G’$一定也有更好方案
对于$G $，最小链覆盖由那$k’-1$条链加上$(C’_i\bigcup X)$这条链共$k’ $条链的方案一定可行，又因为$|S_C|\geq |S_C’|=k’$，故$|S_C|=k’$
原来$G’$中的长度为$k’$的反链仍然成立，又因为$k\leq |S_C|=k’$，这就是$G$中最长的反链，即$k=k’$，此时$|S_C|=k$也成立
综上，当$|V|=n$时命题成立